#!/usr/bin/python
# Filename: Graph.py

# Graph:

# Introduction:
# generally speaking, data structure is about n nodes set N and relationships set R on N.
# if restrict R on direction(precursor and successor) and max counts,
# definations of linear, tree and graph can be following:
# linear: every node has at most 1 precursor and successor;
# tree: every node has at most 1 precursor
# graph: no limit, even can have no restriction on direction(un-directed graph)

# Concept:
# G = (V, E), V is set of vertexes, E is set of edges.
# completed graph, undirected graph, directed graph, labeled graph, weighted(edge) graph,
# degree(in degree, out degree), subgraph, path(simple path(can be simple cycle), length),
# cycle(simple cycle(nodes are different except beginning and end), length of cycle in direced graph >= 2,
# length of cycle in undirected graph should >= 3, length = 2 is just parallel edges(???bad defination))
# acycle graph(directed acycle graph = DAG), rooted graph(include tree), 
# connected graph(conneted, heavy connected and light connected, connected component),
# network(weighted connected graph), free tree(no simple cycle undirected connected graph, |E|=|V|-1)

# Storage:
# 1) adjecency matrix
# it's a matrix M of |N|*|N|, M[i,j] = if <Vi, Vj> in E (or its weight).
# 2) adjecency list
# a) a table of all nodes with label and reference to its adjacent nodes list(it's also adjacent edge list)
# b) several list of nodes(edges) which adjacent to one node linked one by one
# c) directed graph nodes has 2 lists which are in-edges list and out-edges list
# 3) adjecency multilist
# a) a table of all nodes with lable and reference to its first edges
# b) a table of all edges with beginning, end and reference to next edge of beginning and end
# c) directed graph nodes has 2 reference to its first out-edge and in-edge
# d) directed graph edges has 2 reference to its next edges of same beginning and end 
# d.1) reference of first out-edge + its next edge of same beginning is link of node's out-edges set
# d.2) reference of first in-edge + its next edge of same end is link of node's in-edges set

# Traversal:
# add a PH to mark whether a vertex is visited.
# root first, root last, level order(width first).
# spanning tree/forest(paths when traverse a graph).
# time complexity:
# deal with every node and every edge(from each direction)
# a) adjecency matrix: |N|+|N|^2
# b) adjecency list: |N|+|E|(2|E| when undirected graph)

# Topological Sort:
# 1) level order(width first)
# a) get a vertex with 0 in-degree
# b) delete this vertex and its adjacent edges
# c) repeat
# caution: cycle detection.
# a) add a PH to mark whether a vertex rather than delete it
# b) add a PH to mark vertex's in degree, when delete an in-edge, just decrease the degree
# c) add all 0 in-degree vertex into the queue
# d) when queue is empty(no 0 in-degree vertex) and remains un-visited vertex, cycle was detected
# 2) root last
# for each vertex without in-edges:
# a) root last traverse graph from it(add root to the end of sequence, return sequence)
# b) reverse the sequence, it's a topological sort sequence
# cycle detection:
# a) add a PH to mark whether a vertex is visited, un-visited or visiting
# b) if meet a visiting node, cycle is detected; after add to sequence change visiting to visited
# time complexity:
# same as traversal

# ADT:
class Graph:
    '''Graph'''
    def __in__(self):
        self.vertex_num = 0
        self.edge_num = 0

    def first_edge(self, vertex):
        '''return first edge of vertex'''
        pass

    def next_edge(self, edge):
        '''return next edge has same beginning as edge'''
        pass

    def set_edge(self, beginning, end):
        '''set edge's beginning and end'''
        pass

    def del_edge(self, beginning, end):
        '''delete edge(s) from beginning to end'''
        pass

    def is_edge(self, edge):
        '''whether edge is an edge of graph'''
        pass

    def beginning(self, edge):
        '''return the beginning of edge'''
        pass

    def end(self, edge):
        '''return the end of edge'''
        pass

    def weight(self, edge):
        '''return weight of edge'''
        pass
